Nous avons commencé par corriger le DS. Une correction proposée par P.A. Champin est disponible à cette adresse : https://github.com/pchampin/2015-algo-notes/blob/master/2015-11-19%20Correction%20du%20DS.ipynb

Durant ce TD nous avons fait une introduction à la récursivité en jouant à deux jeux :

Lightbot : http://lightbot.com/
Robozzle : http://www.robozzle.com/

Ensuite, nous avons appliqué nos toutes nouvelles connaissances sur la récursivité en implémentant factorielle. Pour rappel, factorielle(n) = 1 x 2 x ... x n. Autrement dit (en récursif) : factorielle(n) = n x factorielle (n - 1), tout en sachant que factorielle(1) = 1. C'est cette forme que l'on va utiliser pour écrire l'algorithme récursif de factiorielle.



In [1]:

    
def fact(n):
    if n == 1: 
        f = 1
    else:
        f = n * fact(n-1)
    return f

fact(4)









    Out[1]:





24

On peut comprendre dans quel ordre s'effectuent les appels récursifs en observant le comportement de factorielle dans PythonTutor par exemple.



In [2]:

    
%load_ext tutormagic



In [3]:

    
%%tutor --lang python3
def facto(n):
    if n == 1: 
        f = 1
    else:
        f = n * facto(n-1)
        print("Ceci est la valeur de n au moment du traitement des appels :" + str(n))
    return f

facto(4)